package week3;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 46. 全排列
 * https://leetcode-cn.com/problems/permutations/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了89.23% 的用户
 * 内存消耗：38.8 MB, 在所有 Java 提交中击败了11.35% 的用户
 *
 *
 *
 */
public class Week3Permutations {

    public List<List<Integer>> permute(int[] nums) {
        int length = nums.length;
        List<List<Integer>> permuteList = new ArrayList<List<Integer>>();

        if (length == 0) {
            // 终止
            return permuteList;
        }
        boolean[] used = new boolean[length];
        List<Integer> path = new ArrayList<Integer>();
        dfs(nums, length, 0, path, used, permuteList);
        return permuteList;
    }

    public void dfs(int[] nums, int length, int depth, List<Integer> path, boolean[] used, List<List<Integer>> list) {
        if(depth == length) {
            // 终止
            list.add(path);
            return;
        }

        for(int size = 0; size < length; size++) {
            if(!used[size]) {
                List<Integer> newPath = new ArrayList<Integer>(path);
                newPath.add(nums[size]);

                boolean[] newUsed = new boolean[length];
                System.arraycopy(used, 0, newUsed, 0, length);
                newUsed[size] = true;
                dfs(nums, length, depth + 1, newPath, newUsed, list);
            }
        }
    }




}
